package te;

/**
 * @author tzp
 * @since 2020/12/17
 */
public class BalanceTree {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    boolean isBalance = true;

    public boolean isBalance(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) return true;
        isBalanceH(root);
        return isBalance;
    }

    //返回树高度
    public int isBalanceH(TreeNode root) {
        //bst: 左右差1, 俩都是bst
        //所有叶子节点高度差不超过1
        if (root == null) return 0;

        int leftH = isBalanceH(root.left);
        int rightH = isBalanceH(root.right);
        if (Math.abs(leftH - rightH) > 1) {
            isBalance = false;
        }
        return Math.max(leftH, rightH) + 1;
    }

    public static void main(String[] args) {
        TreeNode n0 = new TreeNode(0);
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        n0.left = n1;
        n0.right = n2;
        n1.left = n3;
        n3.right = n4;
        System.out.println(new BalanceTree().isBalance(n0));

    }
}
